Search for: All records

Abstract We provide an algorithm to approximate a finitely supported discrete measureμby a measureν_Ncorresponding to a set ofNpoints so that the total variation betweenμandν_Nhas an upper bound. As a consequence ifμis a (finite or infinitely supported) discrete probability measure on [0, 1]^dwith a sufficient decay rate on the weights of each point, thenμcan be approximated byν_Nwith total variation, and hence star-discrepancy, bounded above by (logN)N⁻¹. Our result improves, in the discrete case, recent work by Aistleitner, Bilyk, and Nikolov who show that for any normalized Borel measureμ, there exist finite sets whose star-discrepancy with respect toμis at most ${\left(log\hspace{0.17em}N\right)}^{d-\frac{1}{2}}{N}^{-1}${\left( {\log \,N} \right)^{d - {1 \over 2}}}{N^{ - 1}}. Moreover, we close a gap in the literature for discrepancy in the cased=1 showing both that Lebesgue is indeed the hardest measure to approximate by finite sets and also that all measures without discrete components have the same order of discrepancy as the Lebesgue measure.